// Copyright 2010 Keir Mierle. All rights reserved.

#include <gtest/gtest.h>

#include "using.h"
#include "tt.h"

TEST(BitTwiddles, LowestBitPosition) {
  TranspositionTable<int, int> tt(10);
  tt.Store(1, 5, 4);
  EXPECT_EQ(5, *tt.Lookup(1));

  // Should just overwrite.
  tt.Store(1, 7, 4);
  EXPECT_EQ(7, *tt.Lookup(1));

  // Hash collision; but there's room for both.
  tt.Store(11, 8, 6);
  EXPECT_EQ(7, *tt.Lookup(1));
  EXPECT_EQ(8, *tt.Lookup(11));

  // Another collision; someone's voted off the island.
  tt.Store(21, 9, 2);
  EXPECT_EQ(8,   *tt.Lookup(11));
  EXPECT_EQ(9,   *tt.Lookup(21));
  EXPECT_EQ(NULL, tt.Lookup(1));

  // Yet another collision.
  tt.Store(31, 99, 3);
  EXPECT_EQ(8,   *tt.Lookup(11));
  EXPECT_EQ(99,  *tt.Lookup(31));
  EXPECT_EQ(NULL, tt.Lookup(21));
  EXPECT_EQ(NULL, tt.Lookup(1));

  // An insert that shouldn't collide with anything.
  tt.Store(15, 5, 5);
  EXPECT_EQ(5,   *tt.Lookup(15));
  EXPECT_EQ(8,   *tt.Lookup(11));
  EXPECT_EQ(99,  *tt.Lookup(31));
  EXPECT_EQ(NULL, tt.Lookup(21));
  EXPECT_EQ(NULL, tt.Lookup(1));
}
